#ifndef SOLUTION_H_
#define SOLUTION_H_
#include <vector>
#include <algorithm>

using namespace std;

class Solution{
public:
	vector<vector<int> > threeSum(vector<int>& num){
		vector<vector<int> > result;
		if(num.size() < 3)
			return result;

		sort(num.begin(),num.end());
		vector<int> now(3);
		size_t nNum = num.size();
		for(size_t i=0;i<(nNum-2);i++){
			if((i>0) && (num[i] == num[i-1]))
				continue;
			size_t h = i+1, t = nNum-1;
			while(h<t){
				int tmpSum = num[i]+num[h]+num[t];
				if(tmpSum > 0){
					t--;
				}
				else if(tmpSum < 0){
					h++;
				}
				else{
					if(!result.empty()){
						const vector<int>& last = result[result.size()-1];
						if((num[i]==last[0]) && (num[h]==last[1])){
							h++;
							t--;
							continue;
						}
					}
					now[0]=(num[i]);
					now[1]=(num[h]);
					now[2]=(num[t]);
					result.push_back(now);		
					h++,t--;
				}
			}
		}
		return result;
	}
};
#endif